На белом листе бумаги в клетку
нарисовали три закрашенных прямоугольника так, что их стороны лежат на линиях
сетки, а вершины имеют известные целые координаты. Найти общее количество
закрашенных клеток.
Вход. В трех строках содержится по
четыре целых числа – координаты двух противоположных вершин каждого
прямоугольника. Все числа по модулю не
превышают 100.
Выход. Выведите одно число – количество
закрашенных клеток.
Пример
входа |
Пример
выхода |
2 2 5 6 3 3 7 1 6 4 4 7 |
22 |
двумерный
массив
Анализ алгоритма
Координаты вершин
прямоугольников по
модулю не превышают 100. Следовательно они принимают значения от -100 до
100. Сделаем сдвиг координат на вектор (100, 100) так чтобы все значения стали
неотрицательными (теперь они изменяются от 0 до 200).
Координаты вершин во входных данных находятся в узлах
сетки. Пронумеруем клетки по вертикали и горизонтали, начиная с 0. Тогда
прямоугольник в узлах сетки (a, b) – (c, d) будет
соответствовать прямоугольнику (a, b) – (c – 1, d – 1) на клетках.
Например,
прямоугольнику (2, 2) – (5, 6) в узлах сетки
соответствует прямоугольник (2, 2) – (4, 5) на клетках.
Объявим
двумерный массив m[201][201]. Установим элемент m[i][j] = 1, если один из
входных прямоугольников покрывает клетку (i, j). После обработки всех трех
прямоугольников подсчитаем количество покрытых клеток.
Реализация алгоритма
Объявляем рабочий массив.
#define MAX 210
int m[MAX][MAX];
Функция swap меняем местами числа a и b.
void swap(int& a, int& b)
{
int temp = a; a = b; b = temp;
}
Основная часть программы. Обнуляем массив m.
memset(m, 0, sizeof(m));
Последовательно обрабатываем три прямоугольника.
for (i = 0; i < 3; i++)
{
Читаем координаты очередного прямоугольника (a, b) – (c,
d).
scanf("%d %d %d %d", &a,
&b, &c, &d);
Поменяем местами координаты так, чтобы (a, b) стал левым
нижним углом, а (c, d) правым верхним. После этого будем иметь a < c и b < d.
if (a > c) swap(a, c);
if (b > d) swap(b, d);
Все клетки, которые покрываются прямоугольником (a, b) – (c – 1, d – 1), отмечаем в
массиве m единицами.
Координаты вершин сдвигаем на вектор (MAX / 2, MAX / 2), где MAX – размер массива (индексы
массива не могут быть отрицательными).
for (j = a; j < c; j++)
for (k = b; k < d; k++)
m[j + MAX / 2][k + MAX / 2] = 1;
}
В переменной res подсчитываем
количество покрытых клеток.
res = 0;
for (i = 0; i < MAX; i++)
for (j = 0; j < MAX; j++)
res += m[i][j];
Выводим ответ.
printf("%d\n",res);